package com.bigshen.algorithm.dBinarySearch.solution04FindPeek;

/**
 * 162. Find Peak Element
 * A peak element is an element that is greater than its neighbors.
 *
 * Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
 *
 * The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
 *
 * You may imagine that nums[-1] = nums[n] = -∞.
 *
 * Example 1:
 *
 * Input: nums = [1,2,3,1]
 * Output: 2
 * Explanation: 3 is a peak element and your function should return the index number 2.
 * Example 2:
 *
 * Input: nums = [1,2,1,3,5,6,4]
 * Output: 1 or 5
 * Explanation: Your function can return either index number 1 where the peak element is 2,
 *   or index number 5 where the peak element is 6.
 * Follow up: Your solution should be in logarithmic complexity.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-peak-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    // 峰值问题-  峰顶、左侧向上山腰、右侧向下山腰
    // 二分法取中位值，然后和左右相邻元素相比
    // a. 如果 左邻居 < mid > 右邻居，则mid即为峰顶
    // b. 如果 左邻居 < mid < 右邻居， 则mid处在上山腰，起点右移， start -->
    // c. 否则 左邻居 > mid > 右邻居， 则mid处在下山腰，终点左移， <-- end
    public int findPeakElement(int[] nums) {

        if (null == nums || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;

        while (start + 1 < end) {
            int mid = start + (end-start)/2;
            if (nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]) {
                // mid为峰顶，返回
                return mid;
            }
            if (nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1]) {
                // 上山腰，继续向上/前找，起点右移 start -->
                start = mid;
            } else {  // nums[mid-1] > nums[mid] && nums[mid] > nums[mid+1]
                // 下山腰，继续向后找，终点左移 <-- end
                end = mid;
            }
        }

        return nums[start] > nums[end] ? start : end;

    }

}
